package org.usmile.algorithms.learn.graph.bfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.*;

public class ShortestSingleSourcePath {
    public List<Integer> shortestPath(Graph graph, int source, int target) {
        Queue<Integer> queue = new LinkedList<>();
        int[] prevs = new int[graph.getV()];
        boolean hasPath = false;
        Arrays.fill(prevs, -1);
        queue.offer(source);
        prevs[source] = source;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int w : graph.adj(curr)) {
                if (prevs[w] == -1) {
                    queue.add(w);
                    prevs[w] = curr;
                    if (w == target) {
                        hasPath = true;

                        break;
                    }
                }
            }
        }

        if (!hasPath) {
            return new ArrayList<>();
        }

        LinkedList<Integer> result = new LinkedList<>();
        while (target != source) {
            result.addFirst(target);
            target = prevs[target];
        }

        result.addFirst(source);

        return result;
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(3, 2);

        System.out.println(new ShortestSingleSourcePath().shortestPath(graph, 0, 4));
    }
}
